package com.leetcode;

import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.TreeMap;

/**
 * 295. 数据流的中位数
 * 
 * @author yml
 * 
 *         中位数是有序列表中间的数。如果列表长度是偶数，中位数则是中间两个数的平均值。 例如， [2,3,4]的中位数是 3 [2,3]
 *         的中位数是 (2 + 3) / 2 = 2.5 设计一个支持以下两种操作的数据结构： void addNum(int num) -
 *         从数据流中添加一个整数到数据结构中。 double findMedian() - 返回目前所有元素的中位数。
 */
public class LeetCode295 {

	public static void main(String[] arg0) {
		MedianFinder mf2 = new MedianFinder();
		MedianFinder1 mf = new MedianFinder1();
		mf.addNum(1);
		mf2.addNum(1);
		mf.addNum(2);
		mf2.addNum(2);
		System.out.println("中位数 = " + mf.findMedian());
		System.out.println("中位数 = " + mf2.findMedian());
		mf.addNum(3);
		mf2.addNum(3);
		System.out.println("中位数 = " + mf.findMedian());
		System.out.println("中位数 = " + mf2.findMedian());

	}

	/**
	 * 有序集合(TreeMap无序，实际只是计次) + 双指针处理
	 */
	static class MedianFinder {
		// 有序集合，键为添加的数字，值为添加的次数
	    TreeMap<Integer, Integer> nums;
	    int n;
	    // left和right都是长度为2的数组，起指针作用
	    int[] left;
	    int[] right;

	    public MedianFinder() {
	        nums = new TreeMap<>();
	        n = 0;
	        left = new int[2];
	        right = new int[2];
	    }
	    
	    public void addNum(int num) {
	        nums.put(num, nums.getOrDefault(num, 0) + 1);
	        if (n == 0) {
	            left[0] = right[0] = num;
	            left[1] = right[1] = 1;
	        } else if ((n & 1) != 0) { // n为奇数
	            if (num < left[0]) {
	                decrease(left); //
	            } else {
	                increase(right);
	            }
	        } else { // n为偶数
	            if (num > left[0] && num < right[0]) {
	                increase(left); // 这种情况左指针向Map的ceilingKey指，并且次数为1
	                decrease(right);// 这种情况右指针向Map的floorKey指，并且次数是为Map中保存的值
	            } else if (num >= right[0]) {
	                increase(left);
	            } else {
	                decrease(right);
					System.arraycopy(right, 0, left, 0, 2); // 并且将整个右指针整个赋值给左指针
					// 这时候左右指针是相同的
	            }
	        }
	        n++;
	    }

	    public double findMedian() {
	        return (left[0] + right[0]) / 2.0;
	    }

		/**
		 * 增长
		 */
		private void increase(int[] iterator) {
	        iterator[1]++;
	        if (iterator[1] > nums.get(iterator[0])) {
	            iterator[0] = nums.ceilingKey(iterator[0] + 1);
	            iterator[1] = 1;
	        }
	    }

		/**
		 * 减少
		 */
		private void decrease(int[] iterator) {
	        iterator[1]--;
	        if (iterator[1] == 0) {
	            iterator[0] = nums.floorKey(iterator[0] - 1);
	            iterator[1] = nums.get(iterator[0]);
	        }
	    }
	}

	/**
	 * 优先队列处理
	 */
	static class MedianFinder1 {
		// 如果所求中位数数组总长度为偶数个，两队列大小始终保持相同；总长度为奇数个，小队列比大队列要多一个。
		PriorityQueue<Integer> queueMin; // 从小到大排序
		PriorityQueue<Integer> queueMax; // 从大到小排序

		/** initialize your data structure here. */
		public MedianFinder1() {
			queueMin = new PriorityQueue<Integer>(new Comparator<Integer>() {
				@Override
				public int compare(Integer o1, Integer o2) {
					return (o1 < o2) ? 1 : ((o1 == o2) ? 0 : -1);
				}
			});
			queueMax = new PriorityQueue<Integer>(new Comparator<Integer>() {
				@Override
				public int compare(Integer o1, Integer o2) {
					return (o1 < o2) ? -1 : ((o1 == o2) ? 0 : 1);
				}
			});
		}

		public void addNum(int num) {
			if (queueMin.isEmpty() || num <= queueMin.peek()) {
				// 如果队列小是空的或者num小于等于队列小里面的最大值，把这个数添加到队列小里
				queueMin.offer(num);
				// 队列小的个数比队列大的数量多两个，弹出队列小的最大值并添加到队列大，两个队列的大小此时相同
				if (queueMax.size() + 1 < queueMin.size()) {
					queueMax.offer(queueMin.poll());
				}
			} else {
				queueMax.offer(num);
				// 向队列大中添加数后，如果队列大的个数大于队列小的个数，弹出队列大的最小值添加到队列小中，始终保持队列大的个数小于等于队列小的个数
				if (queueMax.size() > queueMin.size()) {
					queueMin.offer(queueMax.poll());
				}
			}

		}

		public double findMedian() {
			if (queueMin.size() == queueMax.size()) {
				return (queueMin.peek() + queueMax.peek()) / 2.0d;
			}
			return queueMin.peek();
		}
	}

}
